Universe/CPP/Algorithm/Centroid Decomposition.cpp at master · lowjack1/Universe · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/*input
15
15 14
14 11
11 9
11 13
9 6
6 3
3 4
3 2
3 5
2 1
5 7
5 8
7 10
10 12
*/

/*  Centroid Decomposition or Seperator Decomposition
    sub    = subtree size
    tree   = Centroid Tree
    par[i] = parent of ith node in centroid tree
*/

#include <iostream>
#include <vector>
#include <string.h>

const int N = 10005;

std::vector < int > graph[N];
std::vector < int > sub(N);
std::vector < int > tree[N];
int par[N];

/* Function for calculating the size of each subtree */
int dfs(int u, int p)
{
    sub[u] = 1;
    for(auto x: graph[u]) {
        if(x != p and par[x] == -1) {
            sub[u] += dfs(x, u);
        }
    }
    return sub[u];
}

/* Function to find the centroid of a tree rooted at node u and has parent p */
int centroid(int u, int p, int n)
{
    for(auto x: graph[u]) {
        if(x != p and sub[x] > n / 2 and par[x] == -1) {
            return centroid(x, u, n);
        }
    }
    return u;
}

int getcentroid(int u, int p)
{
    //sub.resize(N, 0);
    int sz = dfs(u, p);
    int cntroid = centroid(u, p, sz);
    return cntroid;
}

/* Function for Centroid Decomposition */
int make(int u, int p)
{
    int centroid_root = getcentroid(u, p);
    if(p == -1) {
        p = centroid_root;
    }
    par[centroid_root] = p;
    for(auto x: graph[centroid_root]) {
        if(par[x] == -1) {
            int centroid_subtree = make(x, centroid_root);
            tree[centroid_root].push_back(centroid_subtree);
            tree[centroid_subtree].push_back(centroid_root);
        }
    }
    return centroid_root;
}

int main()
{
    int n;
    std::cin >> n;
    memset(par, -1, sizeof(par));
    for(int i = 1; i < n; ++ i) {
        int x, y;
        std::cin >> x >> y;
        x --, y --;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    make(0, -1);

    /* Output Centroid Tree */
    for(int i = 0; i < n; i ++) {
        std::cout << i + 1 << " -> ";
        for(auto x: tree[i]) {
            std::cout << x + 1 << " ";
        }
        std::cout << "\n";
    }

    for(int i = 0; i < n; i ++) {
        std::cout << par[i] + 1 << " ";
    }
    return 0;
}

/* Expected Output
    1 -> 2
    2 -> 1 3
    3 -> 11 4 2 7
    4 -> 3
    5 -> 8 7
    6 -> 9
    7 -> 5 10 3
    8 -> 5
    9 -> 6 11
    10 -> 12 7
    11 -> 14 9 13 3
    12 -> 10
    13 -> 11
    14 -> 15 11
    15 -> 14
    2 3 3 3 7 9 3 5 11 7 3 10 11 11 14
*/